#include <bits/stdc++.h>

#define N 1005

using namespace std;

int tim[N], val[N];
int dp[N][N];
int dpp[N];

int main(){
    int n, time;
    cin >> time >> n;
    memset(dp, 0, sizeof(dp));
    memset(dpp, 0, sizeof(dpp));
    for(int i = 1; i <= n; i++){
        scanf("%d %d", &tim[i], &val[i]);
    }
    for(int i = 1; i <= n; i++){ //放入前i个物品
        for(int j = time; j >= 0; j--){//背包从大开始，不然会变成完全背包。
            if(j >= tim[i])  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tim[i]] + val[i]);
            else    dp[i][j] = dp[i - 1][j];
        }
    }
    //cout << dp[n][time] << "\n";
    //空间压一维
    for(int i = 1; i <= n; i++){ //放入前i个物品
        for(int j = time; j >= tim[i]; j--){//背包从大开始，不然会变成完全背包。
            dpp[j] = max(dpp[j], dpp[j - tim[i]] + val[i]);
        }
    }
    cout << dpp[time];
    return 0;
}